#include <bits/stdc++.h>

using namespace std;

// 使数组相似的最少操作次数
// 给你两个正整数数组 nums 和 target ，两个数组长度相等
// 在一次操作中，你可以选择两个 不同 的下标 i 和 j
// 其中 0 <= i, j < nums.length ，并且：
// 令 nums[i] = nums[i] + 2 且
// 令 nums[j] = nums[j] - 2
// 如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的
// 请你返回将 nums 变得与 target 相似的最少操作次数
// 测试数据保证nums一定能变得与target相似
// 测试链接 : https://leetcode.cn/problems/minimum-number-of-operations-to-make-arrays-similar/

class Solution 
{
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) 
    {
        int n = nums.size();
        int oddSize = split(nums, n);
        split(target, n);
        sort(nums.begin(), nums.begin() + oddSize);
        sort(nums.begin() + oddSize, nums.end());
        sort(target.begin(), target.begin() + oddSize);
        sort(target.begin() + oddSize, target.end());
        // ans 是总差值，差值每多 4 就要消耗一次操作步数
        long ans = 0; 
        for(int i = 0; i < n; ++i)
        {
            ans += abs(nums[i] - target[i]);
        }
        return ans / 4;
    }

    int split(vector<int>& nums, int n)
    {
        int oddSize = 0;
        // [0...oddSize-1] 区间是奇数
        for(int i = 0; i < n; ++i)
        {
            if((nums[i] & 1) == 1)
            {
                swap(nums[i], nums[oddSize++]);
            }
        }
        return oddSize;
    }
};